import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class ParallelQuickSort {
	private static final int DATASET_SIZE = 128 * 1024;
	public static Set<Thread> pool = Collections
			.<Thread> synchronizedSet(new HashSet<Thread>());
	public static List<QuickSortWorker> available = Collections
			.synchronizedList(new LinkedList<QuickSortWorker>());

	private static class QuickSortWorker extends Thread {
		public static int MIN_BLOCK_SIZE_TO_RUN_IN_PARALLEL = 8192 * 16;

		private final int[] array;
		private int firstIndex;
		private int lastIndex;

		public QuickSortWorker(int[] array, int firstIndex, int lastIndex) {
			super();
			this.array = array;
			this.firstIndex = firstIndex;
			this.lastIndex = lastIndex;
		}

		public void run() {
			if (firstIndex >= 0 && lastIndex >= 0) {
				quickSort(array, firstIndex, lastIndex);
				synchronized (pool) {
					pool.remove(this);
					pool.notifyAll();
				}
			}
		}

		public void go() {
			if (size() < MIN_BLOCK_SIZE_TO_RUN_IN_PARALLEL) {
				run();
			} else {
				pool.add(this);
				this.start();
			}
		}

		public int size() {
			return lastIndex - firstIndex + 1;
		}
	}

	public static void swap(final int A[], int itemIndex, int anotherItemIndex) {
		int temp = A[itemIndex];
		A[itemIndex] = A[anotherItemIndex];
		A[anotherItemIndex] = temp;
	}

	public static int partition(final int array[], int firstIndex, int lastIndex) {
		int pivotValue = array[firstIndex + (lastIndex - firstIndex) / 2];
		while (firstIndex <= lastIndex) {
			while (array[firstIndex] < pivotValue)
				firstIndex++;
			while (array[lastIndex] > pivotValue)
				lastIndex--;
			if (firstIndex <= lastIndex) {
				swap(array, firstIndex, lastIndex);
				firstIndex++;
				lastIndex--;
			}
		}
		return firstIndex;
	}

	public static void quickSort(final int array[], final int firstIndex,
			final int lastIndex) {
		if (firstIndex >= lastIndex)
			return;
		final int pivotIndex = partition(array, firstIndex, lastIndex);
		QuickSortWorker workerLeft;
		workerLeft = new QuickSortWorker(array, firstIndex, pivotIndex - 1);
		workerLeft.go();
		QuickSortWorker workerRight;
		workerRight = new QuickSortWorker(array, pivotIndex, lastIndex);
		workerRight.go();
	}

	public static void main(String[] args) throws InterruptedException {
		// warm up
		int[] originalArray = new int[DATASET_SIZE];
		for (int i = 0; i < originalArray.length; i++) {
			originalArray[i] = (int) (Math.random() * 4000000);
		}
		int[] workingArray = originalArray.clone();
		quickSort(workingArray, 0, workingArray.length - 1);
		// main run
		System.out.println("DATASET SIZE: " + DATASET_SIZE);
		for (int blockSize = DATASET_SIZE / 2048; blockSize <= 2 * DATASET_SIZE; blockSize *= 2) {
			QuickSortWorker.MIN_BLOCK_SIZE_TO_RUN_IN_PARALLEL = blockSize;
			workingArray = originalArray.clone();
			long executionTime = System.currentTimeMillis();
			quickSort(workingArray, 0, workingArray.length - 1);
			synchronized (pool) {
				while (pool.size() > 0) {
					pool.wait();
				}
			}
			executionTime = System.currentTimeMillis() - executionTime;
			System.out.println("Block size: " + blockSize + ". Time: "
					+ ((double) executionTime / 1000) + " s");
			for (int i = 0; i < workingArray.length - 2; i++) {
				if (workingArray[i] > workingArray[i + 1]) {
					System.out.println("[ERROR!] RESULTING ARRAY IS UNSORTED.");
					System.exit(0);
				}
			}
		}
	}
}
